package history.study.dynamic_programming;

// 62. 不同路径

/**
 *  1. dp[i][j] 为到达(i,j)有多少种方式
 *  2. 递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
 *  3. dp[i][0] = 1, dp[0][j] = 1
 *  4. 从前往后进行遍历
 *  5. dp[3][3] = dp[2][3]+dp[3][2]
 *     dp[4][4]= dp[3][4]+dp[4][3]
 */
public class LeetCode_62 {
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) return 0;
        int [][] state = new int[m][n];
        for (int i = 0; i < m; i++)
            state[i][0] = 1;
        for (int i = 0; i < n; i++)
            state[0][i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                state[i][j] = state[i-1][j]+state[i][j-1];
            }
        }
        return state[m-1][n-1];
    }
}
